package n_01;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author ChengMiao
 * @date 2021/6/28 11:53
 * @Desc NO。1 两数之和
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 * 你可以按任意顺序返回答案。
 */
public class Demo {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        int[] arr = getNum(nums, target);

        System.out.println(Arrays.toString(arr));
    }

    /**
     * 我自己的做法
     * 两个循环寻找满足条件的值跳出循环，尽可能减少循环的次数
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        int i = target;
        int[] arr = null;
        for (int i1 = 0; i1 < nums.length - 1; i1++) {
            int k = nums[i1];
            for (int j = i1 + 1; j < nums.length; j++) {
                int j1 = nums[j];
                if (j1 + k == i) {
                    arr = new int[2];
                    arr[0] = i1;
                    arr[1] = j;
                    break;
                }
            }
            if (arr != null) {
                break;
            }

        }

        return arr;
    }

    /**
     * 官方的做法
     * 直接使用一个map 将值对应索引
     * 当找到满足差值的键后直接将索引记录返回
     * @param arr
     * @param target
     * @return
     */
    public static int[] getNum(int[] arr, int target) {
        // 1. 迭代数组的时候使用一个map记录值
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            // 获取 与当前数差值的另一个数的值
            int suffix = target - arr[i];
            // 如果map中存储了该数 且 该数不是其本身 说明当前数与差值 满足条件
            if (map.containsKey(suffix) && map.get(suffix) != i) {

                return new int[]{i, map.get(suffix)};
            }

            // 记录未达到条件时的数与其索引
            map.put(arr[i], i);

        }

        return null;
    }
}
